//找出带权连通无向图中顶点u到v的最短距离。（两种方法实现，图的遍历算法和最短路径算法）
#include <stdio.h>
#include <malloc.h>
#define INF 32767				//定义∞
#define	MAXV 100				//最大顶点个数
typedef char InfoType;

//以下定义邻接矩阵类型
typedef struct
{	int no;						//顶点编号
	InfoType info;				//顶点其他信息
} VertexType;					//顶点类型
typedef struct
{	int edges[MAXV][MAXV];		//邻接矩阵数组
	int n,e;					//顶点数，边数
	VertexType vexs[MAXV];		//存放顶点信息
} MatGraph;						//完整的图邻接矩阵类型


//------------------------------------------------------------
//----邻接矩阵的基本运算算法----------------------------------
//------------------------------------------------------------
void CreateMat(MatGraph &g,int A[MAXV][MAXV],int n,int e) //创建图的邻接矩阵
{
	int i,j;
	g.n=n; g.e=e;
	for (i=0;i<g.n;i++)
		for (j=0;j<g.n;j++)
			g.edges[i][j]=A[i][j];
}
void DispMat(MatGraph g)	//输出邻接矩阵g
{
	int i,j;
	for (i=0;i<g.n;i++)
	{
		for (j=0;j<g.n;j++)
			if (g.edges[i][j]!=INF)
				printf("%3d",g.edges[i][j]);
		else
			printf("%4s","∞");
		printf("\n");
	}
}
void Dijkstra(MatGraph *g, int source, int destination) {
	int dist[MAXV];
	int visited[MAXV] = {0};
	
	for (int i = 0; i < g->n; i++) {
		dist[i] = INF;
	}
	dist[source] = 0;
	
	for (int i = 0; i < g->n - 1; i++) {
		int min_dist = INF;
		int u = -1;
		
		for (int j = 0; j < g->n; j++) {
			if (!visited[j] && dist[j] < min_dist) {
				min_dist = dist[j];
				u = j;
			}
		}
		
		if (u == -1) break;
		visited[u] = 1;
		
		for (int v = 0; v < g->n; v++) {
			if (!visited[v] && g->edges[u][v] != 0) {
				if (dist[u] + g->edges[u][v] < dist[v]) {
					dist[v] = dist[u] + g->edges[u][v];
				}
			}
		}
	}
	
	printf("The shortest distance from %d to %d is %d\n", source, destination, dist[destination]);
}
//邻接表
//以下定义邻接表类型
typedef struct ANode
{	int adjvex;					//该边的邻接点编号
	struct ANode *nextarc;		//指向下一条边的指针
	int weight;					//该边的相关信息，如权值（用整型表示）
} ArcNode;						//边结点类型
typedef struct Vnode
{	InfoType info;				//顶点其他信息
	int count;					//存放顶点入度,仅仅用于拓扑排序
	ArcNode *firstarc;			//指向第一条边
} VNode;						//邻接表头结点类型
typedef struct 
{	VNode adjlist[MAXV];		//邻接表头结点数组
	int n,e;					//图中顶点数n和边数e
} AdjGraph;						//完整的图邻接表类型
void CreateAdj(AdjGraph *&G,int A[MAXV][MAXV],int n,int e) //创建图的邻接表
{
	int i,j;
	ArcNode *p;
	G=(AdjGraph *)malloc(sizeof(AdjGraph));
	for (i=0;i<n;i++)								//给邻接表中所有头结点的指针域置初值
		G->adjlist[i].firstarc=NULL;
	for (i=0;i<n;i++)								//检查邻接矩阵中每个元素
		for (j=n-1;j>=0;j--)
			if (A[i][j]!=0 && A[i][j]!=INF)			//存在一条边
			{	p=(ArcNode *)malloc(sizeof(ArcNode));	//创建一个结点p
				p->adjvex=j;
				p->weight=A[i][j];
				p->nextarc=G->adjlist[i].firstarc;	//采用头插法插入结点p
				G->adjlist[i].firstarc=p;
			}
	G->n=n; G->e=n;
}
void DispAdj(AdjGraph *G)	//输出邻接表G
{
	int i;
	ArcNode *p;
	for (i=0;i<G->n;i++)
	{
		p=G->adjlist[i].firstarc;
		printf("%3d: ",i);
		while (p!=NULL)
		{
			printf("%3d[%d]→",p->adjvex,p->weight);
			p=p->nextarc;
		}
		printf("∧\n");
	}
}
void DestroyAdj(AdjGraph *&G)		//销毁图的邻接表
{	int i;
	ArcNode *pre,*p;
	for (i=0;i<G->n;i++)			//扫描所有的单链表
	{	pre=G->adjlist[i].firstarc;	//p指向第i个单链表的首结点
		if (pre!=NULL)
		{	p=pre->nextarc;
			while (p!=NULL)			//释放第i个单链表的所有边结点
			{	free(pre);
				pre=p; p=p->nextarc;
			}
			free(pre);
		}
	}
	free(G);						//释放头结点数组
}

int visited[MAXV]={0};
void DFS(AdjGraph *G,int source,int dest,int currentlist,int *shortMin)  
{
	if(source==dest) {
		if(currentlist<*shortMin){
			*shortMin = currentlist;
		}
		return;
	}
	visited[source] = 1;//标记已经访问过了
	ArcNode*p = G->adjlist[source].firstarc;
	while(p!=NULL)
	{
		if(!visited[p->adjvex])
		{
			DFS(G,p->adjvex,dest,currentlist+p->weight,shortMin);
		}
		p = p->nextarc;
	}
	visited[source] = 0;
}


int FindMinPaht(AdjGraph*&g,int source,int dest)
{
	int shortMin = INF;
	DFS(g,source,dest,0,&shortMin);
	return (shortMin==INF)?-1:shortMin;
}



int main()
{
	printf("找出带权连通无向图中顶点u到v的最短距离。（两种方法实现，图的遍历算法和最短路径算法）\n");
	MatGraph g9a3;
	int A9a3[MAXV][MAXV]={
		{  0,  7, 12,  3,INF},//0
		{  7,  0,  4,INF,  5},//1
		{ 12,  4,  0,INF,  3},//2
		{  3,INF,INF,  0,  7},//3
		{INF,  5,  3,  7,  0} //4
		
	};
	int n9a3=5, e9a3=7;
	int source = 0;
	int destination = 0;
	CreateMat(g9a3,A9a3,n9a3,e9a3);			//建立《教程》中图8.35的邻接矩阵
	printf("图G的邻接矩阵:\n");
	DispMat(g9a3);					//输出邻接矩阵
	
	printf("最短路径法：\n");
	printf("输入顶点u和v：");
	scanf("%d%d",&source,&destination);
	Dijkstra(&g9a3,source,destination);
	
	
	AdjGraph* g1;
	CreateAdj(g1,A9a3,n9a3,e9a3);
	printf("图的遍历算法：\n");
	printf("图G的邻接表:\n");
	DispAdj(g1);
	printf("输入顶点u和v：");
	scanf("%d%d",&source,&destination);
	int path = FindMinPaht(g1,source,destination);
	if(path==-1)
		printf("no path!\n");
	else
		printf("The shortest distance from %d to %d is %d\n", source, destination, path);
	
	DestroyAdj(g1);
	return 0;
}
